加速经典算法效率，突破现实技术瓶颈：图神经网络与组合优化读书会启动

导语

现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。

为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！

读书会背景

算法是一种用于解决问题的有序步骤的集合，现实中很多问题的解决依赖于相应算法的设计与求解，如页面推荐的PageRank算法，整数规划的分支定界算法。传统算法都是人类专家设计的，随着人工智能技术的不断发展，出现了越来越多的算法自动学习算法的成功案例，前一个“算法”一般指以神经网络为代表的的人工智能算法，后一个“算法”则指传统的经典算法，这便是算法神经化求解的缘由。

算法神经化求解的主要研究动机是解决经典算法算不动的问题。很多经典算法虽然在现实中很有用，但往往因其昂贵的计算复杂度难以大规模使用，如很多的组合优化算法因其问题的NP难属性，求解难度随问题规模呈指数级增长。算法神经化求解主要采用神经网络模型和数据驱动训练的方式自动学习经典算法的求解，求解效率往往很高，通用性也强，但也因缺乏理论保证无法保证算得准。

算法神经化求解的意义也是显而易见的。加速经典算法的计算效率可以极大提高经典算法在现实中的适用范围和应用价值。AI for Science 中有很大一部分是模拟科学计算的问题，归根到底其实就是经典算法的神经化求解。物流运输、生产调度、芯片设计等一大类现实问题的瓶颈技术难点，也在于其背后NP难运筹优化算法的高效求解。

在算法神经化求解方向上，图神经网络是一个强有力的工具。实际上任何对象都可以适用图表示的框架。比如图像，可以看作是由附近的像素组成的图。文本可以看作彼此相连的一系列目标。更广泛地说，自然界中没有被人为设计编排进某个框架或序列的东西，都非常自然地表现为图结构。基于图神经网络的求解方法能够充分利用图结构的特性，进而实现对高复杂度算法的高效近似求解。

本次读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络以及算法神经化求解在 AI for Science 中的应用等方面。我们将邀请一些业内专家分享他们在这些领域的最新研究成果。本次读书会将为参会者提供一个学术交流的平台，以共同探讨图神经网络在算法神经化求解的发展与现实应用。同时希望能够激发与会者的学术兴趣，进一步推动相关领域的研究和应用发展。

读书会框架介绍

在过去几年中，随着神经网络和深度学习技术的快速发展，图神经网络用于组合优化问题的求解已经取得了显著的进步，尤其是在端到端求解、局部改进求解以及处理自然输入等方面。

同时，算法推理技术的出现让深度学习模型模仿经典算法，实现了传统算法的泛化性和神经网络的最优解的完美结合。此外，图神经网络的出现还极大推动了AI在基础科学中的应用，实现了人工智能与基础学科的深度融合，从而极大地促进了相关学科的发展。

本次读书会旨在分享这些领域的最新研究成果，以促进图神经网络和算法神经化求解的研究和应用的进一步发展。

发起人团队介绍

范长俊，国防科技大学系统工程学院副教授，研究方向是人工智能与复杂系统。以第一作者或通讯作者在Nature Machine Intelligence、Nature Communications、AAAI等顶级期刊和会议发表论文多篇。

黄文炳，中国人民大学高瓴人工智能学院助理教授、博导。研究方向包括几何机器学习理论方法、几何机器学习在机器人感知与决策任务上的应用、科学知识嵌入的机器学习等。尤其在图神经网络GNN方面，提出了训练深度图神经网络的方法DropEdge和面向大规模图的图神经网络高效训练方法AS-GCN。

报名参加读书会

本读书会适合参与的对象

• 基于图神经网络与算法神经化求解相关研究，特别是对算法对齐、组合优化、几何图神经网络和AI for Science相关研究中的模型、方法有浓厚兴趣的一线科研工作者；
• 能基于读书会所列主题和文献进行深入探讨，可提供适合的文献和主题的朋友；
• 能熟练阅读英文文献，并对复杂科学充满激情，对世界的本质充满好奇的探索者；
• 想锻炼自己科研能力或者有出国留学计划的高年级本科生及研究生。

本读书会谢绝参与的对象

为确保专业性和讨论的聚焦，本读书会谢绝脱离读书会文本和复杂科学问题本身的空泛的哲学和思辨式讨论；不提倡过度引申在社会、人文、管理、政治、经济等应用层面的讨论。我们将对参与人员进行筛选，如果出现讨论内容不符合要求、经提醒无效者，会被移除群聊并对未参与部分退费，解释权归集智俱乐部所有。

运行模式

本季读书会预计讨论分享8次，按暂定框架贯次展开；每周进行线上会议，由 1-2 名读书会成员以PPT讲解的形式领读相关论文，与会者可以广泛参与讨论，会后可以获得视频回放持续学习。

举办时间

从 2023 年 6 月 14 日开始，每周三晚上 19:00-21:00，持续时间预计8周。我们也会对每次分享的内容进行录制，剪辑后发布在集智斑图网站上，供读书会成员回看，因此报名的成员可以根据自己的时间自由安排学习时间。

参与方式

此次读书会为线上闭门读书会，采用的会议软件是腾讯会议（请提前下载安装）。在扫码完成报名并添加负责人微信后，负责人会将您拉入交流社区（微信群），入群后告知具体的会议号码。

报名方式

第一步：扫码填写报名信息。

扫码报名

第二步：填写信息后，付费299元。第三步：添加负责人微信，拉入对应主题的读书会社区（微信群）。本读书会可开发票，请联系相关负责人沟通详情。

针对学生的退费机制

读书会通过共学共研的机制，围绕前沿主题进行内容梳理和沉淀，所以针对于学生，可以通过参与共创任务，获取积分，积分达到退费标准之后，可以直接退费。

加入社区后可以获得的资源

• 在线会议室沉浸式讨论：与主讲人即时讨论交流

• 交互式播放器高效回看：快速定位主讲人提到的术语、论文、大纲、讨论等重要时间点

• 高质量的主题微信社群：硕博比例超过80%的成员微信社区，闭门夜谈和交流

• 超多学习资源随手可得：从不同尺度记录主题下的路径、词条、前沿解读、算法、学者等

• 参与社区内容共创任务：读书会笔记、百科词条、公众号文章、论文解读分享等不同难度共创任务，在学习中贡献，在付出中收获。

• 共享追踪主题前沿进展：在群内和公众号分享最新进展，领域论文速递

参与共创任务，共建学术社区

• 读书会笔记：在交互式播放器上记录术语和参考文献

• 集智百科词条：围绕读书会主题中重要且前沿的知识概念梳理成词条。例如：

• 论文解读分享：认领待读列表中的论文，以主题报告的形式在社区分享

• 论文摘要翻译：翻译社区推荐论文中的摘要和图注

• 公众号文章：以翻译整理或者原创生产形式生产公众号文章，以介绍前沿进展。例如：

• 论文翻译

• 科普文章翻译

PS：具体参与方式可以加入读书会后查看对应的共创任务列表，领取任务，与运营负责人沟通详情，上述规则的最终解释权归集智俱乐部所有。

阅读材料

主题一：图神经网络与经典算法对齐

简介

DeepMind提出的神经算法推理技术能够将经典算法用深度学习模型进行模仿，并实现了传统算法的泛化性和神经网络的最优解的完美结合。该技术采用算法对齐的思想，即将算法划分成多个部分，每个部分由神经算法建模。在此基础上，提出了新的GNN架构和训练机制，可有效解决复杂的组合优化问题，同时提高算法的泛化能力。

主要参考文献

1. Veličković P, Blundell C. Neural algorithmic reasoning[J]. Patterns, 2021, 2(7): 100273.

这篇文章提出神经算法推理的概念，通过用深度学习方法更好地模仿算法，让深度学习实现算法的高度可泛化性，同时保留对问题的最优解。

1. Neural Execution of Graph Algorithms. Yiding Feng, Chelsea Finn, and Stefanie Jegelka. NeurIPS 2019.

这篇文章提出了一种基于图神经网络的图算法执行框架，旨在直接对图算法进行执行而非预测。它将算法操作（如遍历）作为操作和查询节点的一部分，使用图神经网络来学习如何执行这些操作。

1. K. Xu, J. Li, M. Zhang, S. S. Du, K.-I. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020b.

这篇文章引入了算法对齐的概念，这一概念构成了神经算法推理的核心思想。

1. Deac A I, Veličković P, Milinkovic O, et al. Neural algorithmic reasoners are  implicit planners[J]. Advances in Neural Information  Processing  Systems,  2021,  34:  15529-15542.

这篇文章以隐式的方式介绍了基于GNN的算法推理框架，具有较好的泛化性能。

1. Ibarz B, Kurin V, Papamakarios G, et al. A generalist neural algorithmic learner[C]. Learning on Graphs Conference. PMLR, 2022: 2: 1-2: 23.

这篇文章提出一个通用的神经算法推理器，该模型依赖单一参数集的GNN，能够同时学习诸如排序、搜索、贪心算法、动态规划、图算法、字符串排序和几何算法等经典算法任务，并且达到专家模型的平均水平。

主题二：图神经网络与组合优化——端到端求解

简介：图神经网络端到端求解组合优化问题的方式主要有两种：自回归和非自回归。这里有一篇关于面向组合优化问题的图学习综述文章可以提前学习一下。

自回归简介

自回归方式是指在图神经网络中，将解的生成过程建模为一个逐步生成的过程。每一步生成一 个解的一部分，并使用已生成的部分来指导下一步的生成。这种方式的优点是可以在生成过程中动态地考虑约束条件和优化目标，但缺点是生成速度相对较慢。

主要参考文献

1. Khalil E, Dai H, Zhang Y, et al. Learning combinatorial optimization algorithms over graphs[J]. Advances in neural information processing systems, 2017, 30.

这篇文章探讨了组合优化问题的一般形式，提出了一种使用自回归方式学习图上组合优化问题的求解算法。

1. Fan C, Zeng L, Sun Y, et al. Finding key players in complex networks through deep reinforcement learning[J]. Nature machine intelligence, 2020, 2(6): 317-324.

这篇文章提出基于深度强化学习框架，该框架可以在小型网络上进行训练，以理解复杂网络系统的组织原则，从而帮助我们设计更加抗攻击和抗故障的网络。

视频资料推荐：利用强化学习寻找复杂系统的关键节点，范长俊

https://campus.swarma.org/course/1808

1. Bello I, Pham H, Le Q V, et al. Neural combinatorial optimization with reinforcement learning[J]. arXiv preprint arXiv:1611.09940, 2016.

这篇文章基于自回归的方式采用强化学习求解组合优化问题，将整个问题的求解过程分解为多个步骤，并设计了一个可以自适应调整生成顺序的网络结构。

1. Amos B, Kolter J Z. Optnet: Differentiable optimization as a layer in neural networks[C]//International Conference on Machine Learning. PMLR, 2017: 136-145.

这篇文章提出一种新的神经网络架构，将优化问题作为单独的layer集成到更大的端到端可训练的深度网络中。

1. Kool W, Van Hoof H, Welling M. Attention, learn to solve routing problems![J]. arXiv preprint arXiv:1803.08475, 2018.

该论文提出了一种基于注意力机制的图神经网络架构，用于解决路由问题。该方法能够有效地学习路由问题的结构特征，并在测试集上取得了优异的性能。

视频资料推荐：注意力模型学习求解路径问题，牟牧云

https://campus.swarma.org/course/1052

非自回归简介

非自回归方式是指在图神经网络中，将整个问题的求解过程作为一个整体进行求解，一次性 输出最终的解。这种方式的优点是求解速度较快，但缺点是不能动态地考虑约束条件和优化目标。

主要参考文献

1. Li Z, Chen Q, Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search[J]. Advances in neural information processing systems, 2018, 31.

这篇论文主要介绍了一种结合图卷积网络（GCN）和引导树搜索（Guided Tree Search）的组合优化算法，用于解决包括旅行商问题（TSP）和车辆路径问题（VRP）等一系列NP难问题。该算法使     用GCN模型来从图形输入中提取特征，并将其输入到引导树搜索中，引导树搜索使用GCN模型提供   的启发式信息来指导搜索过程。

视频资料推荐：结合图卷积网络的组合优化和树搜索，刘晶

https://campus.swarma.org/course/1086

1. Fu Z H, Qiu K B, Zha H. Generalize a small pre-trained model to arbitrarily large tsp instances[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(8): 7474- 7482.

这篇文章尝试采用监督学习方式，训练一个小规模的模型，利用图采样、图转换以及热图合并等一 系列技术，构建可重复用于任意规模TSP实例的热图。此外，通过输入热图到强化学习方法(蒙特卡  洛树搜索)，以指导搜索高质量的解决方案。

1. Nazari M, Oroojlooy A, Snyder L, et al. Reinforcement learning for solving the vehicle routing problem[J]. Advances in neural information processing systems, 2018, 31.

这篇文章采用图卷积神经网络和强化学习来解决车辆路径问题。

1. Chalumeau F, Coulon I, Cappart Q, et al. Seapearl: A constraint programming solver guided by reinforcement learning[C]//Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings 18. Springer International Publishing, 2021: 392-409.

这篇文章将约束满足问题（CSP）建模成简单的、无向的三部图。在该图上，每个变量、可能的取   值和约束都用节点表示。当且仅当一个变量涉及到一个约束，或者当一个值在一个变量的可选取值 集合中时，相应的节点才由一条边连接。

1. Pogančić M V, Paulus A, Musil V, et al. Differentiation of blackbox combinatorial solvers[C]//International Conference on Learning Representations. 2020.

图神经网络在处理自然输入等上游任务中发挥着重要作用，可直接从自然输入如图片、语音和文本等中提取特征，并应用于组合优化问题的求解。这篇论文模型的自然输入为图片，利用神经网络解决TSP、最短路径等组合优化问题。

主题三：图神经网络与组合优化——局部改进求解

简介

图神经网络采用局部改进求解组合优化问题主要包括两种方式，一种是改进精确算法，如分支定 界法中的分支用分类学习代替；另一种则是局部改进启发式算法，如改进模拟退火中的退火机制。

局部改进精确算法

主要参考文献

1. Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks[J]. Advances in neural information processing systems, 2019, 32.

这篇文章将MILP问题的变量和约束建模成二部图，基于建模的二部图，采用GCN和模仿学习   改进分支策略。

1. Khalil E, Le Bodic P, Song L, et al. Learning to branch in mixed integer programming[C]. Proceedings of the AAAI Conference on Artificial Intelligence. 2016, 30(1).
   这篇论文将图神经网络应用于决策树的分支选择，从而改进了传统的分支策略，从而解决混合 整数规划（MIP）问题。
2. Chen X Y, Tian Y D. Learning to perform local rewriting for combinatorial optimization. In: Proceedings of the 33rd Conference on Neural Information Processing Systems. Vancouver, Canada: Curran Associates, Inc., 2019. 6278−6289

这篇文章提出了一个基于深度强化学习的组合优化问题搜索模型 NeuRewriter, 它和局部搜索具有相似的算法流程,  即首先随机构造一个可行解,  在该初始解的基础上通过局部搜索不断提高解的质量。

局部改进启发式算法

主要参考文献

1. Mills K, Ronagh P, Tamblyn I. Finding the ground state of spin Hamiltonians with reinforcement learning[J]. Nature Machine Intelligence, 2020, 2(9): 509-517.

这篇文章采用强化学习方法改进模拟退火中的退火机制。

1. Deudon M, Cournut P, Lacoste A, et al. Learning heuristics for the tsp by policy gradient[C]//Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15. Springer International Publishing, 2018: 170-181.

神经网络框架被扩展到TSP问题上，该框架的求解效果优于高性能的启发式算法。

1. Xin L, Song W, Cao Z, et al. NeuroLKH: Combining deep learning model with Lin- Kernighan-Helsgaun heuristic for solving the traveling salesman problem[J]. Advances in Neural Information Processing Systems, 2021, 34: 7472-7483.

这篇文章采用GCN对节点特征进行编码，结合LKH启发式算法，能够在保证算法效率的同时，   进一步提高求解精度。

主题四：几何图神经网络

简介：无论是微观世界中的分子、蛋白质、抗体、RNA，还是宏观世界中的机械系统、不同形状的物体等，构成了一类重要的数据形态——几何图。与社交网络中的拓扑图不同，几何图中的节点占据了一定的空间位置，需要满足某些内蕴的物理性质，比如对称性，导致传统的图神经网络难以处理几何图。近年来，不变和等变图神经网络考虑了对称性，具有良好的解释性、泛化性和通用性，能有效实现几何图的处理和分析。几何图神经网络在物理系统模拟、蛋白质折叠预测（如主题五中的RoseTTAFold论文）、抗体设计（如主题五中的MEAN论文）等问题上得到了成功应用。

不变图神经网络

将数据映射到某个不变特征，使得原始数据无论做任何变换，不变特征均不受影响。

1. K. T. Schütt, H. E. Sauceda, P.-J. Kindermans, A. Tkatchenko, and K.-R. Müller. SchNet – A deep learning architecture for molecules and materials. J.Chem.Phys 2018.

简称Schnet，早期的不变图神经网络。

1. Johannes Gasteiger, Janek Groß, Stephan Günnemann. Directional Message Passing for Molecular Graphs. ICLR 2020.

简称DimNet，在GNN引入了带方向的消息传播。

1. Johannes Gasteiger, Florian Becker, Stephan Günnemann. GemNet: Universal Directional Graph Neural Networks for Molecules. NeurIPS 2021.

简称GemNet，一种不变GNN，考虑了球面坐标，效果值得信赖。由DimNet的主要作者打造。

等变图神经网络

对模型输入做一定的变换之后，模型输出做同样的变换。

1. Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, Patrick Riley. Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds. 2018.

这篇论文简称张量场网络TFN，是最早同时满足旋转、平移等变的GNN，在分子动力模拟上进行验证，领域必读文章。

1. Victor Garcia Satorras, Emiel Hoogeboom, Max Welling. E(n) Equivariant Graph Neural Networks. ICML 2021.

瞩目的EGNN，目前被广泛使用的等变图神经网络模型，领域必读文章。

1. Johannes Brandstetter, Rob Hesselink, Elise van der Pol, Erik J Bekkers, Max Welling. Geometric and Physical Quantities Improve E(3) Equivariant Message Passing. ICLR 2022.

简称SEGNN，在EGNN基础上引入了higer-degree 不可约表示，基于这篇文章可以概括性学习E3不变表示相关知识。

主题五：图神经网络在科学计算中的应用

简介

中国科学院院士鄂维南教授提出基础学科发展新的曙光：AI for Science将人工智能与基础科学深度融合。科学领域的许多问题本质上是对物理系统的处理和分析，而物理系统是可以建模成图谱。因此，图神经网络是AI for Science领域的基础工具，极大推动了AI在分子动力学模拟、材料设计、药物发现等任务上的应用前景。

主要参考文献

1. 数学（GNN与偏微分方程，PDE）

Iakovlev V, Heinonen M, Lähdesmäki H. Learning continuous-time pdes from sparse data with graph neural networks[J]. arXiv preprint arXiv:2006.08956, 2020.

1. 物理（GNN与spin glasss）

Fan C, Shen M, Nussinov Z, et al. Searching for spin glass ground states through deep reinforcement learning[J]. Nature Communications, 2023, 14(1): 725.

1. 化学

Tian Xie, Jeffrey C. Grossman. Crystal Graph Convolutional Neural Networks for an Accurate and Interpretable Prediction of Material Properties. Physical Review Letters, 2018.

简称CGCNN，最早的晶体性质预测工作，提出multi-graph来建模晶体周期性

1. 生物

Wang J, Ma A, Chang Y, et al. scGNN is a novel graph neural network framework for single-cell RNA-Seq analyses[J]. Nature communications, 2021, 12(1): 1882.

使用图神经网络形式化和聚合细胞-细胞关系，并使用左截断混合高斯模型对异质性基因表达模式进行建模，成功应用到单细胞RNA测序（scRNA-Seq）任务。

Minkyung Baek, Frank DiMaio, et al. Accurate prediction of protein structures and interactions using a three-track neural network. Science, 2021.

简称RoseTTAFold，解决了蛋白质折叠问题。

Xiangzhe Kong, Wenbing Huang, Yang Liu. Conditional Antibody Design as 3D Equivariant Graph Translation. ICLR, 2023.

简称MEAN，使用了等变图神经网络完成抗体CDR区域1D氨基酸序列和3D结构的同时生成和优化。

相关学习路径

关于本次读书会的论文列表与相关学习资源，可以扫码查看

公众号文章

点击“阅读原文”，报名读书会